/**
 * @ClassName Offer04
 * @Description 剑指 Offer 04. 二维数组中的查找
 * @Author clockTown
 * @Date 2021/8/16 8:42
 * @Version 1.0
 */
class Offer04 {
}

/**
 * 暴力
 */
class Offer04V0 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j]==target){
                    return true;
                }
            }
        }
        return false;
    }
}

/**
 * v1 二分查找
 */
class Offer04V1 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return false;
        }
        int i = matrix.length - 1;
        int j = 0;
        while (i >= 0 && j < matrix[0].length){
            if(matrix[i][j] > target) {
                i--;
            } else if(matrix[i][j] < target) {
                j++;
            } else {
                return true;
            }
        }
        return false;
    }
}